A pseudorandom number generator (PRNG) is an algorithm to generate a sequence of numbers that approximate the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state. PRNGs are important in practice for simulations, and particularly central in the practice of cryptography.
A linear congruential generator is one of the earliest and best known pseudorandom number generator algorithms. The generator is defined by the recurrence relationship: Xi+1=(aXi+c) mod p, where Xi is the sequence of random values, p is the modulus, a is the multiplier, c is the increment, and X0 is the seed value. While linear congruential generators are capable of producing decent pseudorandom numbers, they are extremely sensitive to the choice of c, m, and a. In addition, they should not be used in applications where high quality randomness is crucial, such as cryptographic applications.
An inverse congruential generator is a type of nonlinear congruential pseudorandom number generator, which uses the modular multiplicative inverse to generate the next number in a sequence. Inverse congruential generators do a better job at providing high quality randomness than linear congruential generators. The standard formula for an inverse congruential generator is: Xi+1=(aXi−1+c) (mod p).
Another pseudorandom number generator is the multiply-with-carry (MWC) generator. The MWC generator is similar to the linear congruential generator, except that the formula has two evolving values, instead of one evolving value (i.e., the Xi sequence) with the linear congruential generator. In a MWC generator, the c value also evolves in addition to the Xi value. The formulas used for the generator are as follows: Xi+1=(aXi+ci) mod p; and ci+1=(aXi+ci−−Xi+1)/p. The MWC generator provides more unpredictability to the recurrence relationship due to the changing carry value affecting the cycle length. It may also be extended by using the multiplicative inverse of the inverse congruential generator in the MWC formula.
A variation of the MWC generator expands the generator to a lag-r implementation, with the recurrence equations as follows: Xi+1=(aXi−r+ci) mod p; ci+1=(aXi+ci−−Xi+1)/p, where r is the defined lag for the variation. Again, this expansion provides a different level of unpredictability to the recurrence relationship.
The above generators all provide for varying degrees of randomness in a pseudorandom number generator. However, they all operate over integers. This limitation presents difficulties when implementing the above formulas in a hardware environment. In a resource-constrained environment, computing these formulas over integers may not be as efficient as would be desirable. As such, a mechanism to generate pseudorandom bit sequences while accounting for hardware processing power and capacity would be beneficial.